package org.apache.commons.graph.collections

import com.gitee.wsl.collections.queue.Queue
import com.gitee.wsl.ext.list.pop
import com.gitee.wsl.ext.list.push
import org.apache.commons.graph.utils.Assertions
import kotlin.math.floor
import kotlin.math.ln
import kotlin.math.sqrt

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * A Fibonacci Heap implementation based on
 * [University of Science and Technology of
 * China](https://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm) lesson.
 *
 *
 * **Note 1**: this class is NOT thread safe!
 *
 *
 * **Note 2**: this class doesn't support `null` values
 *
 * @param <E> the type of elements held in this collection.
</E> */
class FibonacciHeap<E>( /* @Nullable */
                        /**
                         * The comparator, or null if priority queue uses elements'
                         * natural ordering.
                         */
                        private val comparator: Comparator<in E>? = null
) : Queue<E> {

    /**
     * A simple index of stored elements.
     */
    private val elementsIndex: MutableSet<E> = HashSet()

    /**
     * The number of nodes currently in `H` is kept in `n[H]`.
     */
    override var size: Int = 0

    /**
     * `t(H)` the number of trees in the root list.
     */
    private var trees = 0

    /**
     * `m(H)` the number of marked nodes in `H`.
     */
    private var markedNodes = 0

    /**
     * The root of the tree containing a minimum key `min[H]`.
     */
    private var minimumNode: FibonacciHeapNode<E>? = null

    /**
     * Creates a [FibonacciHeap] that orders its elements according to the specified comparator.
     *
     * @param comparator the comparator that will be used to order this queue.
     * If null, the natural ordering of the elements will be used.
     */

    /**
     * {@inheritDoc}
     *
     * <pre>FIB-HEAP-INSERT(H, x)
     * 1  degree[x]  0
     * 2  p[x]  NIL
     * 3  child[x]  NIL
     * 4  left[x]  x
     * 5  right[x]  x
     * 6  mark[x]  FALSE
     * 7  concatenate the root list containing x with root list H
     * 8  if min[H] = NIL or key[x] &lt; key[min[H]]
     * 9     then min[H]  x
     * 10  n[H]  n[H] + 1</pre>
     */
    override fun add(element: E): Boolean {
        Assertions.checkNotNull(element, "Null elements not allowed in this FibonacciHeap implementation.")

        // 1-6 performed in the node initialization
        val node = FibonacciHeapNode(element)

        // 7-9 performed in the #moveToRoot( FibonacciHeapNode<E> ) method
        moveToRoot(node)

        // 10  n[H] <- n[H] + 1
        size++

        elementsIndex.add(element)

        return true
    }

    /**
     * {@inheritDoc}
     */
    override fun addAll(elements: Collection<E>): Boolean {
        for (element in elements) {
            add(element)
        }

        return true
    }

    /**
     * Implements the `CASCADING-CUT(H,y)` function.
     *
     * <pre>CASCADING-CUT(H,y)
     * 1  z  p[y]
     * 2  if z  NIL
     * 3     then if mark[y] = FALSE
     * 4             then mark[y]  TRUE
     * 5             else CUT(H,y,z)
     * 6                  CASCADING-CUT(H,z)</pre>
     *
     * @param y the target node to apply CASCADING-CUT
     */
    private fun cascadingCut(y: FibonacciHeapNode<E>) {
        // z <- p[y]
        val z = y.parent

        // if z != NIL
        if (z != null) {
            // if mark[y] = FALSE
            if (!y.isMarked) {
                // then mark[y]  TRUE
                y.isMarked = true
                markedNodes++
            } else {
                // else CUT(H,y,z)
                cut(y, z)
                // CASCADING-CUT(H,z)
                cascadingCut(z)
            }
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun clear() {
        minimumNode = null
        size = 0
        trees = 0
        markedNodes = 0
        elementsIndex.clear()
    }

    /**
     * Compare the given objects according to to the specified comparator if not null,
     * according to their natural ordering otherwise.
     *
     * @param o1 the first [FibonacciHeap] node to be compared
     * @param o2 the second [FibonacciHeap] node to be compared
     * @return a negative integer, zero, or a positive integer as the first argument is
     * less than, equal to, or greater than the second
     */
    private fun compare(o1: FibonacciHeapNode<E>, o2: FibonacciHeapNode<E>): Int {
        if (comparator != null) {
            return comparator.compare(o1.element, o2.element)
        }
        val o1Comparable// it will throw a ClassCastException at runtime
                = o1.element as Comparable<E>?
        return o1Comparable!!.compareTo(o2.element)
    }

    /**
     * Implements the `CONSOLIDATE(H)` function.
     *
     * <pre>CONSOLIDATE(H)
     * 1 for i  0 to D(n[H])
     * 2      do A[i]  NIL
     * 3 for each node w in the root list of H
     * 4      do x  w
     * 5         d  degree[x]
     * 6         while A[d]  NIL
     * 7            do y  A[d]
     * 8               if key[x] &gt; key[y]
     * 9                  then exchange x  y
     * 10                FIB-HEAP-LINK(H,y,x)
     * 11                A[d]  NIL
     * 12                d  d + 1
     * 13         A[d]  x
     * 14 min[H]  NIL
     * 15 for i  0 to D(n[H])
     * 16      do if A[i]  NIL
     * 17            then add A[i] to the root list of H
     * 18                 if min[H] = NIL or key[A[i]]  key[min[H]]
     * 19                    then min[H]  A[i]</pre>
     */
    private fun consolidate() {
        if (isEmpty()) {
            return
        }

        // D( n[H] ) <= log_phi( n[H] )
        // -> log_phi( n[H] ) = log( n[H] ) / log( phi )
        // -> D( n[H] ) = log( n[H] ) / log( phi )
        val arraySize = (floor(ln(size.toDouble()) / LOG_PHI).toInt())

        // 1  for i <- 0 to D(n[H])
        val nodeSequence: MutableList<FibonacciHeapNode<E>?> = ArrayList(arraySize)
        for (i in 0..<arraySize) {
            // 2      do A[i] <- NIL
            nodeSequence.add(i, null)
        }

        var numRoots = 0

        // 3  for each node x in the root list of H
        // 4  do x &larr; w
        var x = minimumNode

        if (x != null) {
            numRoots++
            x = x.right

            while (x != minimumNode) {
                numRoots++
                x = x!!.right
            }
        }

        while (numRoots > 0) {
            // 5  d <- degree[x]
            var degree = x!!.degree
            val next = x.right

            // 6  while A[d] != NIL
            while (nodeSequence[degree] != null) {
                // 7  do y <- A[d]
                var y = nodeSequence[degree]

                // 8  if key[x] > key[y]
                if (compare(x!!, y!!) > 0) {
                    // 9  exchange x <-> y
                    val pointer = y
                    y = x
                    x = pointer
                }

                // 10  FIB-HEAP-LINK(H,y,x)
                link(y, x)

                // 11  A[d] <- NIL
                nodeSequence[degree] = null

                // 12  d <- d + 1
                degree++
            }

            // 13  A[d] <- x
            nodeSequence[degree] = x

            x = next
            numRoots--
        }

        // 14  min[H] <- NIL
        minimumNode = null

        // 15  for i <- 0 to D(n[H])
        for (pointer in nodeSequence) {
            if (pointer == null) {
                continue
            }
            if (minimumNode == null) {
                minimumNode = pointer
            }

            // 16 if A[i] != NIL
            // We've got a live one, add it to root list.
            if (minimumNode != null) {
                //  First remove node from root list.
                moveToRoot(pointer)
            }
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun contains(element: E): Boolean {
        if (element == null) {
            return false
        }

        return elementsIndex.contains(element)
    }

    /**
     * {@inheritDoc}
     */
    override fun containsAll(elements: Collection<E>): Boolean {

        for (o in elements) {
            if (!contains(o)) {
                return false
            }
        }

        return true
    }

    /**
     * Implements the `CUT(H,x,y)` function.
     *
     * <pre>CUT(H,x,y)
     * 1  remove x from the child list of y, decrementing degree[y]
     * 2  add x to the root list of H
     * 3  p[x]  NIL
     * 4  mark[x]  FALSE</pre>
     *
     * @param x the node has to be removed from `y` children
     * @param y the node has to be updated
     */
    private fun cut(x: FibonacciHeapNode<E>, y: FibonacciHeapNode<E>) {
        // add x to the root list of H
        moveToRoot(x)

        // remove x from the child list of y, decrementing degree[y]
        y.decraeseDegree()
        // p[x] <- NIL
        x.setParentNode(null)

        // mark[x] <- FALSE
        x.isMarked = false
        markedNodes--
    }

    /**
     * {@inheritDoc}
     */
    override fun element(): E {
        if (isEmpty()) {
            throw NoSuchElementException()
        }
        return peek()!!
    }

    /**
     * {@inheritDoc}
     */
    override fun isEmpty(): Boolean {
        return minimumNode == null
    }

    /**
     * {@inheritDoc}
     */
    override fun iterator(): MutableIterator<E> {
        throw UnsupportedOperationException()
    }

    /**
     * Implements the `FIB-HEAP-LINK(H, y, x)` function.
     *
     * <pre>FIB-HEAP-LINK(H, y, x)
     * 1  remove y from the root list of H
     * 2  make y a child of x, incrementing degree[x]
     * 3  mark[y]  FALSE</pre>
     *
     * @param y the node has to be removed from the root list
     * @param x the node has to to become fater of `y`
     */
    private fun link(y: FibonacciHeapNode<E>, x: FibonacciHeapNode<E>) {
        // 1 remove y from the root list of H
        y.left.setRightNode(y.right)
        y.right.setLeftNode(y.left)

        y.setParentNode(x)

        if (x.child == null) {
            // 2 make y a child of x, incrementing degree[x]
            x.setChildNode(y)
            y.setRightNode(y)
            y.setLeftNode(y)
        } else {
            y.setLeftNode(x.child!!)
            y.setRightNode(x.child!!.right)
            x.child!!.setRightNode(y)
            y.right.setLeftNode(y)
        }

        x.incraeseDegree()

        // 3 mark[y] <- FALSE
        y.isMarked = false
        markedNodes++
    }

    /**
     * Moves the target node in the `H` root nodes.
     *
     * @param node the node has to be moved in the `H` root nodes
     * @see .add
     * @see .consolidate
     * @see .cut
     */
    private fun moveToRoot(node: FibonacciHeapNode<E>) {
        // 8'  if min[H] = NIL
        if (isEmpty()) {
            // then min[H] <- x
            minimumNode = node
        } else {
            // 7 concatenate the root list containing x with root list H
            node.left.setRightNode(node.right)
            node.right.setLeftNode(node.left)

            node.setLeftNode(minimumNode!!)
            node.setRightNode(minimumNode!!.right)
            minimumNode!!.setRightNode(node)
            node.right.setLeftNode(node)

            // 8''  if key[x] < key[min[H]]
            if (compare(node, minimumNode!!) < 0) {
                // 9     then min[H] <- x
                minimumNode = node
            }
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun offer(e: E): Boolean {
        return add(e)
    }

    /**
     * {@inheritDoc}
     */
    override fun peekOrNull(): E? {
        if (isEmpty()) {
            return null
        }

        return minimumNode!!.element
    }

    /**
     * {@inheritDoc}
     *
     * <pre>FIB-HEAP-EXTRACT-MIN(H)
     * 1  z  min[H]
     * 2  if z  NIL
     * 3      then for each child x of z
     * 4               do add x to the root list of H
     * 5                  p[x]  NIL
     * 6           remove z from the root list of H
     * 7           if z = right[z]
     * 8              then min[H]  NIL
     * 9              else min[H]  right[z]
     * 10                   CONSOLIDATE(H)
     * 11           n[H]  n[H] - 1
     * 12  return z</pre>
     */
    override fun pollOrNull(): E? {
        // 2  if z &ne; NIL
        if (isEmpty()) {
            return null
        }

        // 1  z <- min[H]
        val z = minimumNode!!
        var numOfKids = z.degree

        var x = z.child
        var tempRight: FibonacciHeapNode<E>

        while (numOfKids > 0) {
            // 3  for each child x of z
            tempRight = x!!.right

            // 4  do add x to the root list of H
            moveToRoot(x)

            // 5  p[x] <- NIL
            x.setParentNode(null)

            x = tempRight
            numOfKids--
        }

        // 6  remove z from the root list of H
        z.left.setRightNode(z.right)
        z.right.setLeftNode(z.left)

        // 7  if z = right[z]
        if (z == z.right) {
            // 8  min[H] <- NIL
            minimumNode = null
        } else {
            // 9  min[H] <- right[z]
            minimumNode = z.right
            // 10  CONSOLIDATE(H)
            consolidate()
        }

        // 11  n[H] <- n[H] - 1
        size--

        val minimum = z.element
        elementsIndex.remove(minimum)
        // 12  return z
        return minimum
    }


    /**
     * The potential of Fibonacci heap `H` is then defined by
     * `t(H) + 2m(H)`.
     *
     * @return The potential of this Fibonacci heap.
     */
    fun potential(): Int {
        return trees + 2 * markedNodes
    }

    /**
     * {@inheritDoc}
     */
    fun removeAndGet(): E {
        // FIB-HEAP-EXTRACT-MIN(H)
        if (isEmpty()) {
            throw NoSuchElementException()
        }
        return poll()!!
    }

    /**
     * {@inheritDoc}
     */
    override fun remove(element: E): Boolean = poll() != null

    /**
     * {@inheritDoc}
     */
    override fun removeAll(c: Collection<E>): Boolean {
        throw UnsupportedOperationException()
    }

    /**
     * {@inheritDoc}
     */
//    override fun retainAll(c: Collection<E>): Boolean {
//        throw UnsupportedOperationException()
//    }

    /**
     * {@inheritDoc}
     */
//    fun size(): Int {
//        return size
//    }

    /**
     * {@inheritDoc}
     */
//     fun toArray(): Array<E> {
//        throw UnsupportedOperationException()
//    }

    /**
     * {@inheritDoc}
     */
//     fun <T> toArray(a: Array<T>): Array<T> {
//        throw UnsupportedOperationException()
//    }

    /**
     * Creates a String representation of this Fibonacci heap.
     *
     * @return String of this.
     */
    override fun toString(): String {
        if (minimumNode == null) {
            return "FibonacciHeap=[]"
        }

        // create a new stack and put root on it
        val stack = mutableListOf<FibonacciHeapNode<E>>()
        stack.push(minimumNode!!)

        val buf = StringBuilder("FibonacciHeap=[")

        // do a simple breadth-first traversal on the tree
        while (stack.isNotEmpty()) {
            var curr = stack.pop()
            buf.append(curr)
            buf.append(", ")

            if (curr.child != null) {
                stack.push(curr.child!!)
            }

            val start = curr
            curr = curr.right

            while (curr != start) {
                buf.append(curr)
                buf.append(", ")

                if (curr.child != null) {
                    stack.push(curr.child!!)
                }

                curr = curr.right
            }
        }

        buf.append(']')

        return buf.toString()
    }

    companion object {
        /**
         * The *Phi* constant value.
         */
        private val LOG_PHI = ln((1 + sqrt(5.0)) / 2)
    }
}
